
var res []string


func restoreIpAddresses(s string) []string {
    res = make([]string, 0)
    backTracking(s, 0, []string{})
    return res
}

func backTracking(s string, startIndex int, path []string){
    if len(path) == 4 && startIndex==len(s) {
        tem := path[0] + "." + path[1] + "." + path[2] + "." + path[3]
        res = append(res, tem)
        return
    }

    for i:=startIndex; i<len(s); i++ {
        if len(path) <= 4 && isNormalIp(s, startIndex, i){
            path = append(path, s[startIndex:i+1])
        } else {
            continue
        }
        backTracking(s, i+1, path)
        path = path[:len(path)-1]
    }

}

func isNormalIp(s string, start int, end int) bool {
    ipNum, err := strconv.Atoi(s[start:end+1])
    if err != nil {
        return false
    }
    if s[start] == '0' && start!=end {
        return false
    }
    if ipNum > 255 {
        return false
    }
    return true
}